◀ Prev · Parts · Full · Next ▶

layout: Wide · Narrow · Centered

Cancellation gives Pr [ C i = C ] ≥ 2 n ( n − 1 ) {\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}} . Thus the probability that the algorithm succeeds is at least 1 − ( 1 − 2 n ( n − 1 ) ) m {\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}} . For m = n ( n − 1 ) 2 ln ⁡ n {\displaystyle m={\frac {n(n-1)}{2}}\ln n} , this is equivalent to 1 − 1 n {\displaystyle 1-{\frac {1}{n}}} . The algorithm finds the min cut with probability 1 − 1 n {\displaystyle 1-{\frac {1}{n}}} , in time O ( m n ) = O ( n 3 log ⁡ n ) {\displaystyle O(mn)=O(n^{3}\log n)} .

Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible).cite-ref-21[21]cite-ref-22[22] It is not currently known if all algorithms can be derandomized without significantly increasing their running time.cite-ref-2-23-0[23] For instance, in computational complexity, it is unknown whether P = BPP,cite-ref-2-23-1[23] i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

There are specific methods that can be employed to derandomize particular randomized algorithms:

• the method of conditional probabilities, and its generalization, pessimistic estimators

• discrepancy theory (which is used to derandomize geometric algorithms)

• the exploitation of limited independence in the random variables used by the algorithm, such as the pairwise independence used in universal hashingcite-ref-24[24]

• the use of expander graphs (or dispersers in general) to amplify a limited amount of initial randomness (this last approach is also referred to as generating pseudorandom bits from a random source, and leads to the related topic of pseudorandomness)

• changing the randomized algorithm to use a hash function as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by brute-forcing all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)

◀ Prev · Parts · Full · Next ▶